package difficult;

import java.util.HashSet;
import java.util.Set;
import util.PrintUtils;

public class Solution_85 {

    public int maximalRectangle(char[][] matrix) {
        int rst = 0;
        if (matrix.length == 0 || matrix[0].length == 0) {
            return rst;
        }
        int[][] arrays = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == '1') {
                    int r_min = Integer.MAX_VALUE;
                    for (int r = i; r >= 0; r--) {
                        if (matrix[r][j] != '1') {
                            break;
                        }
                        if (j > 0 && matrix[r][j-1] == '1') {
                            int r_num = arrays[r][j-1] + 1;
                            if (r_num < r_min) {
                                r_min = r_num;
                            }
                        } else {
                            r_min = 1;
                        }
                        int sum = (i - r + 1) * r_min;
                        rst = Math.max(sum, rst);
                    }
                    arrays[i][j] = j > 0 && matrix[i][j-1] == '1' ? arrays[i][j-1] + 1 : 1;
                }
            }
//            System.out.println();
        }
        return rst;
    }

    public static void main(String[] args) {
        Solution_85 model = new Solution_85();
        System.out.println(model.maximalRectangle(
            new char[][]{{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'}}));
        System.out.println(model.maximalRectangle(new char[][]{}));
        System.out.println(model.maximalRectangle(new char[][]{{'0'}}));
        System.out.println(model.maximalRectangle(new char[][]{{'1'}}));
        System.out.println(model.maximalRectangle(new char[][]{{'0', '0'}}));
        System.out.println(model.maximalRectangle(new char[][]{{'0','0','0','0','0','0','1'},{'0','0','0','0','1','1','1'},{'1','1','1','1','1','1','1'},{'0','0','0','1','1','1','1'}}));
        System.out.println(model.maximalRectangle(new char[][]{{'0', '1'}, {'1', '0'}}));
        //                PrintUtils.transfer("[[\"0\",\"0\",\"0\",\"0\",\"0\",\"0\",\"1\"],[\"0\",\"0\",\"0\",\"0\",\"1\",\"1\",\"1\"],[\"1\",\"1\",\"1\",\"1\",\"1\",\"1\",\"1\"],[\"0\",\"0\",\"0\",\"1\",\"1\",\"1\",\"1\"]]");
    }
}
